package dp;

import java.util.LinkedList;
import java.util.List;

import Tree.BinaryTreeCreate;
import Tree.TreeNode;

//构造二叉搜索树
//1 -- N  构造所有的二叉搜索树
public class UniqueBST {

	public static void main(String[] args) {
		UniqueBST uniqueBST = new UniqueBST();
		List<TreeNode> list = uniqueBST.generateTrees(3);
		for (TreeNode treeNode : list) {
			System.out.println("--in---");
			BinaryTreeCreate.inOrder(treeNode);
			System.out.println("--pre---");
			BinaryTreeCreate.preOrder(treeNode);
			System.out.println("----");
		}
	}
	public List<TreeNode> generateTrees(int n) {
		return generateSubtrees(1, n);
	}
	private List<TreeNode> generateSubtrees(int start, int end) {
		List<TreeNode> res = new LinkedList<TreeNode>();
		if (start > end) {
			res.add(null); // empty tree
			return res;
		}
		List<TreeNode> leftSubtrees, rightSubtrees;
		//比如说 1 的左边只能是null
		for (int i = start; i <= end; ++i) {
			//比i小的在左边，比i大的在右边
			leftSubtrees = generateSubtrees(start, i - 1);
			rightSubtrees = generateSubtrees(i + 1, end);
            System.out.println("left: " + leftSubtrees.size() + " right: " + rightSubtrees.size());
            //可以说是递归的思想的还是，也可以说是动态规划
            //比如我们要求4 为根结点的时候(F(4,4))
            //我们只需得到3的List<TreeNode> ,将left指针指向其中的所有节点即可得到所有的结果
            //当然可能我们根节点是3，左边是2的List<TreeNode> ，右边的是只有4的List<TreeNode>(此时只包括4)
            //根据我们在I中得到的，就是两者的积，所以我们可以很清楚的知道
            //分别让left 指向左子树中的跟结点 ，right循环指向右子树中的跟结点
			for (TreeNode left : leftSubtrees) {
				for (TreeNode right : rightSubtrees) {
					TreeNode root = new TreeNode(i);
					root.left = left;
					root.right = right;
					res.add(root);
				}
			}
		}
		return res;
	}
}
